package slidingWindow;

import java.util.HashMap;
import java.util.Map;

public class MinWindow {

    /**
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
     * 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     *
     * 注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
     *
     * @param args
     */
    public static void main(String[] args) {

    }

    //动态滑动窗口，需要确定一个临界值来固定窗口的大小，然后进行元素收集
    //总结：收集结果的时机很重要
    public static String minWindow(String s, String t){
        int s_len = s.length();
        int t_len = t.length();
        //用来存放原始数据，元素以及对应元素的个数
        HashMap<Character, Integer> t_set = new HashMap<>();
        //初始化原始数据
        for (int i = 0; i < t_len; i++){
            t_set.put(t.charAt(i), t_set.getOrDefault(t.charAt(i), 0) + 1);
        }
        //存放窗口中的数据
        HashMap<Character, Integer> win_set = new HashMap<>();
        //存放结果
        int begin = 0;
        int minLen = Integer.MAX_VALUE;
        //左边界
        int left = 0;
        for (int right = 0; right < s_len; right++){
            //处理右边界
            if (t_set.keySet().contains(s.charAt(right))){
                win_set.put(s.charAt(right), win_set.getOrDefault(s.charAt(right), 0)+1);
            }

            //控制左边界使之能够符合条件，当条件不满足时，指针不能够移动
            while (check(t_set, win_set)){
                //求最小值，在满足条件的时候进行收集
                if (minLen > right - left + 1){
                    begin = left;
                    minLen = right - left + 1;
                }
                //处理左边界
                if (win_set.keySet().contains(s.charAt(left))){
                    win_set.put(s.charAt(left), win_set.get(s.charAt(left)) - 1);
                }
                left++;
            }


        }

        return minLen==Integer.MAX_VALUE?"":s.substring(begin, begin + minLen);
    }

    //用于检查一个map中是否包含另一个集合的所有元素
    public static boolean check(HashMap<Character, Integer> map1, HashMap<Character, Integer> map2){
        for (Map.Entry<Character, Integer> entry : map1.entrySet()) {
            if (map2.getOrDefault(entry.getKey(), 0) < entry.getValue()){
                return false;
            }
        }
        return true;
    }

    public String minWindow01(String s, String t) {
        //滑动窗口的条件
        int t_len = t.length();
        HashMap<Character, Integer> t_set = new HashMap<>();
        for (int i = 0; i < t_len; i++){
            t_set.put(t.charAt(i), t_set.getOrDefault(t.charAt(i), 0) + 1);
        }
        //字符串的长度
        int s_len = s.length();

        int right = -1;
        //存放结果
        HashMap<Character, Integer> win_set = new HashMap<>();
        int minLen = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;

        for (int i = 0; i < s_len; i++){
            //右边界向右移动，达到符合条件的地点
            while (right + 1 < s_len && !check(t_set, win_set)){
                right++;
                win_set.put(s.charAt(right), win_set.getOrDefault(s.charAt(right), 0) + 1);
            }
            //满足条件时，收集结果
            if (check(t_set, win_set)){
                if (minLen > right - i + 1){
                    minLen = right - i + 1;
                    start = i;
                    end = right;
                }
            }
            //左边界向右移动
            win_set.put(s.charAt(i), win_set.get(s.charAt(i)) - 1);
        }
        return minLen == Integer.MAX_VALUE?"":s.substring(start, end+1);
    }
}
